package com.ruoyi.learn.java.algorithm.tree;

import java.util.LinkedList;
import java.util.Queue;

public class HzlBuilder {


    /**
     * 二叉树节点
     */
    class Node{
        public int val;
        public Node left;
        public Node right;
        public Node(int val){
            this.val = val;
        }
    }

    /**
     * 构建二叉树
     *    1
     *  2   3
     * 4 5 6 7
     * @param arr
     * @return
     */
    public Node buildNode(Integer[] arr){
        // 创建根节点
        Node root = new Node(arr[0]);
        Node current = root;
        Queue<Node> queue = new LinkedList();
        queue.add(root);
        int i = 1;

//        for(int i = 1; i < arr.length; i++){

        while (!queue.isEmpty()){
            if(i == arr.length){
                // 树已构建完成
                break ;
            }
            // 空节点
            current = queue.poll();


            // 左子树
            if(arr[i] == null){
                current.left = null;
            }else {
                Node node = new Node(arr[i]);
                current.left = node;
                queue.add(node);
            }

            i++;
            // 右子树
            if(arr[i] == null){
                current.right = null;
            }else {
                Node node = new Node(arr[i]);
                current.right = node;
                queue.add(node);
            }
            i++;
        }
        return root;
    }

    /**
     * 层序遍历
     * @param node
     */
    public void printAllNode(Node node){
       if(node == null){
           System.out.print("不可能空树    ");
           return;
       }
       Queue<Node> queue = new LinkedList();
       queue.add(node);
       while (!queue.isEmpty()){
           Node newNode = queue.poll();
           if(newNode == null){
               System.out.print("当前节点"+ "空节点" + " ");
               continue;
           }else {
               System.out.print("当前节点"+ + newNode.val + " ");
           }
           if(newNode.left != null){
               queue.add(newNode.left);
           }else if(newNode.left == null){
               queue.add(null);
//               System.out.print("左子树为空  ");
           }
           if(newNode.right != null){
               queue.add(newNode.right);
           }else if(newNode.right == null){
               queue.add(null);

//               System.out.print("右子树为空  ");
           }
       }
    }

    /**
     * 递归遍历
     * @param node
     */
    public void printAllNodeBySelf(Node node){
        if(node == null){
            System.out.print("空树    ");
            return;
        }else {
            System.out.print("当前节点值为" + node.val + " ");
        }
        // 递归遍历左子树
        printAllNodeBySelf(node.left);
        // 递归遍历右子树
        printAllNodeBySelf(node.right);
    }

    /**
     * 递归遍历(左中右)
     * @param node
     */
    public void printAllLeftMidRightNodeBySelf(Node node){
        // 递归遍历左子树
        if(node.left != null){
            printAllLeftMidRightNodeBySelf(node.left);
        }else {
            System.out.print("左子树为空  ");
        }
        if(node == null){
            System.out.print("空树    ");
            return;
        }else {
            System.out.print("当前节点值为" + node.val + " ");
        }
        // 递归遍历右子树
        if(node.right != null){
            printAllLeftMidRightNodeBySelf(node.right);
        }else {
            System.out.print("右子树为空  ");
        }
    }

    /**
     * 递归遍历(右中左)
     * @param node
     */
    public void printAllRightMidLeftNodeBySelf(Node node){
        // 递归遍历右子树
        if(node.right != null) {
            printAllRightMidLeftNodeBySelf(node.right);
        }else {
            System.out.print("右子树为空  ");
        }
        if(node == null){
            System.out.print("空树    ");
            return;
        }else {
            System.out.print("当前节点值为" + node.val + " ");
        }
        // 递归遍历左子树
        if(node.left != null) {
            printAllRightMidLeftNodeBySelf(node.left);
        }else {
            System.out.print("左子树为空  ");
        }
    }




    /**
     *
     * 规律 n的左节点位置  2n+1   n的右节点位置 2n+2
     * 2n+1  父节点位置 n
     * 2n+2  父节点位置 n
     * (x-1)/2急父节点位置
     * 输入层序序列 {3,9,20,21,22,15,7,111,222,null,null,null,null,null,null}   利用java 构建二叉树
     *                   3
     *         9                  20
     *      21         22       15          7
     *   111 222  null null null null  null null
     * @param args
     */
    public static void main(String[] args) {
        Integer[] arr = {3,9,20,21,22,15,7,111,222,null,null,null,null,null,null};
        Node root = new HzlBuilder().buildNode(arr);
        System.out.println(root.val);
        // 层序遍历所有节点
        System.out.println("\n层序遍历所有节点\n");
        new HzlBuilder().printAllNode(root);
        System.out.println("\n中序递归遍历\n");
        // 递归遍历(中序遍历)
        new HzlBuilder().printAllNodeBySelf(root);

        System.out.println("\n\n递归遍历(左中右)");
        new HzlBuilder().printAllLeftMidRightNodeBySelf(root);

        System.out.println("\n\n递归遍历(右中左)");
        new HzlBuilder().printAllRightMidLeftNodeBySelf(root);

    }




}
